package src.leetcode.everyday.hard_3363;


/**
 * @Author: 李逸重
 * @CreateTime: 2025-08-07
 * @Description:
 * @Version: 1.0
 */
public class maxCollectedFruits {
    public static void main(String[] args) {
        System.out.println(new Solution().maxCollectedFruits(new int[][]{{1,2,3,4},{5,6,8,7},{9,10,11,12},{13,14,15,16}}));
    }
}

class Solution {
    public int maxCollectedFruits(int[][] fruits) {
        int n = fruits.length;
        int ans = 0;
        for (int i = 0; i < n; i++) {
            ans += fruits[i][i];
            fruits[i][i] = 0;
        }

        int[][] dp = new int[n][n];
        dp[0][0] = fruits[n - 1][0];
        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= i; j++) {
                int pre = dp[i - 1][j];
                if (j > 0) pre = Math.max(pre, dp[i - 1][j - 1]);
                if (j < n - 1) pre = Math.max(pre, dp[i - 1][j + 1]);
                dp[i][j] = pre + fruits[n - 1 - j][i];
            }
        }
        ans += dp[n - 1][0];

        dp[0][0] = fruits[0][n - 1];
        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= i; j++) {
                int pre = dp[i - 1][j];
                if (j > 0) pre = Math.max(pre, dp[i - 1][j - 1]);
                if (j < n - 1) pre = Math.max(pre, dp[i - 1][j + 1]);
                dp[i][j] = pre + fruits[i][n - 1 - j];
            }
        }
        ans += dp[n - 1][0];

        return ans;
    }
}